package com.erbao.datastructurearithmetic.tyro;

import java.util.*;

/**
 * @author CaoBaoYin
 * @since 2021/8/7 11:53
 */
public class Class7 {

    public static void main(String[] args) {
        /*TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(6);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(7);
        System.out.println(isValidBST(root));*/

        // mockStack();

        /*int testTimes = 10000000;
        int maxSize = 100;
        int maxValue = 10000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode<Integer> root = generateBalanceIntValueTree(maxSize, maxValue);
            if (isBinarySearchTree(root) ^ isBinarySearchTreeV2(root)) {
                System.out.println(levelOrderBottom(root));
                System.out.println("bad");
                break;
            }
        }
        System.out.println("nice");*/

        TreeNode<Integer> root = generateTreeWithArray(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,5,1});
        System.out.println(pathSum(root, 22));
    }

    /**
     * 收集达标路径
     * @param root 树
     * @param targetSum 路径和达标值
     * 示例：树{5,4,8,11,null,13,4,7,2,null,null,5,1}；和 22；结果 [[5, 4, 11, 2], [5, 8, 4, 5]]。
     */
    private static List<List<Integer>> pathSum(TreeNode<Integer> root, int targetSum) {
        ArrayList<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;

        processPathSum(root, 0, targetSum, new LinkedList<Integer>(), list);

        return list;
    }

    /**
     *
     * @param root 树
     * @param sum 根结点到当前结点的路径和
     * @param targetSum 达标路径和
     * @param pathList 全程通用的一个路径list
     * @param list 返回list
     */
    private static void processPathSum(TreeNode<Integer> root, int sum, int targetSum, LinkedList<Integer> pathList, ArrayList<List<Integer>> list) {
        pathList.add(root.val);
        int curSum = sum + root.val;// 根结点到当前结点的路径和
        // 如果是叶子结点
        if (root.left==null && root.right==null) {
            if (curSum == targetSum) {
                list.add(new ArrayList<>(pathList));
                pathList.remove(pathList.size() - 1);
                return;
            }
        }

        // 如果不是叶子结点
        if (root.left != null) {
            processPathSum(root.left, curSum, targetSum, pathList, list);
        }
        if (root.right != null) {
            processPathSum(root.right, curSum, targetSum, pathList, list);
        }
        pathList.remove(pathList.size() - 1);
    }

    /**
     * 通过数组生成二叉树
     * @param array 数组。示例：[5,4,8,11,null,13,4,7,2,null,null,null,1]
     * @return 树的根结点
     */
    private static <T> TreeNode<T> generateTreeWithArray (T[] array) {
        if (array == null) return null;
        if (array.length == 1) return new TreeNode<>(array[0]);

        Queue<TreeNode<T>> queue = new LinkedList<>();
        TreeNode<T> root = new TreeNode<>(array[0]);
        queue.offer(root);

        int index = 1;
        while (index < array.length) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode<T> node = queue.poll();

                T leftValue = array[index++];
                if (leftValue!=null) {
                    node.left = new TreeNode<>(leftValue);
                    queue.offer(node.left);
                } else {
                    node.left = null;
                }

                T rightValue = array[index++];
                if (rightValue != null) {
                    node.right = new TreeNode<>(rightValue);
                    queue.offer(node.right);
                } else {
                    node.right = null;
                }
            }
        }

        return root;
    }

    private static boolean isHasPathSum;

    /**
     * 判断是否有目标路径和
     * @param root 树
     * @param targetSum 目标和
     */
    private static boolean hasPathSum(TreeNode<Integer> root, int targetSum) {
        if (root == null) return false;
        if (root.left==null && root.right==null) return root.val == targetSum;

        isHasPathSum = false;
        processPathSum (root, 0, targetSum);
        return isHasPathSum;
    }

    /**
     *
     * @param root 结点
     * @param sum 到上一个结点的和（即不含当前结点）
     * @param targetSum 目标和
     */
    private static void processPathSum(TreeNode<Integer> root, int sum, int targetSum) {
        // 如果找到了，就不要继续了
        if (isHasPathSum) return;
        // 叶子结点
        int curSum = root.val + sum;
        if (root.left == null && root.right==null) {
            isHasPathSum = (curSum == targetSum);
            return;
        }

        if (root.left != null) {
            processPathSum(root.left, curSum, targetSum);
        }

        if (root.right != null) {
            processPathSum(root.right, curSum, targetSum);
        }
    }

    /**
     * 判断平衡树
     */
    private static boolean isBalanced(TreeNode<?> root) {
        if (root == null) return true;

        // 左子树和右子树平衡，且当前树平衡
        if (Math.abs(Class6.maxDepth(root.left) - Class6.maxDepth(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right))
            return true;

        return false;
    }

    /**
     * 判断平衡树
     */
    private static boolean isBalancedV2(TreeNode<?> root) {
        if (root == null) return true;

        return processBalance(root).isBalanced;
    }

    private static BalanceTreeInfo processBalance(TreeNode<?> root) {
        if (root == null) return new BalanceTreeInfo(true, 0);

        if (root.left == null && root.right==null)
            return new BalanceTreeInfo(true, 1);

        BalanceTreeInfo leftBalanceInfo = processBalance(root.left);
        BalanceTreeInfo rightBalanceInfo = processBalance(root.right);
        BalanceTreeInfo balanceTreeInfo = new BalanceTreeInfo();
        boolean balanced = false;
        if (leftBalanceInfo.isBalanced && rightBalanceInfo.isBalanced && Math.abs(leftBalanceInfo.maxHeight - rightBalanceInfo.maxHeight)<2) {
            balanced = true;
        }
        balanceTreeInfo.setMaxHeight(Math.max(leftBalanceInfo.maxHeight, rightBalanceInfo.maxHeight)+1);
        balanceTreeInfo.setBalanced(balanced);
        return balanceTreeInfo;
    }

    private static class BalanceTreeInfo {
        private boolean isBalanced;
        private int maxHeight;

        public BalanceTreeInfo() {
        }

        public BalanceTreeInfo(boolean isBalanced, int maxHeight) {
            this.isBalanced = isBalanced;
            this.maxHeight = maxHeight;
        }

        public boolean isBalanced() {
            return isBalanced;
        }

        public void setBalanced(boolean balanced) {
            isBalanced = balanced;
        }

        public int getMaxHeight() {
            return maxHeight;
        }

        public void setMaxHeight(int maxHeight) {
            this.maxHeight = maxHeight;
        }
    }

    /**
     * 层级遍历到叶子节点
     */
    private static List<List<Integer>> levelOrderBottom(TreeNode<Integer> root) {
        List<List<Integer>> list = new LinkedList<>();
        if (root == null) {
            return list;
        }

        // 结点放入队列
        Queue<TreeNode<Integer>> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            // 一层结点的个数
            int size = queue.size();

            ArrayList<Integer> levelList = new ArrayList<>(queue.size());
            for (int i = 0; i < size; i++) {
                TreeNode<Integer> poll = queue.poll();
                levelList.add(poll.val);

                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }// 边遍历，边放入下一层的结点，遍历完成，队列中就全部是下一层的结点
            list.add(0, levelList);
        }

        return list;
    }

    /**
     * 数组模拟栈结构
     */
    private static void  mockStack (){
        // 创建栈
        int[] stack = new int[10];
        int index = 0;

        // 入栈
        for (int i = 0; i < 10; i++) {
            stack[index++] = i;
        }
        //出栈
        for (int i = 0; i < 10; i++) {
            System.out.println(stack[--index]);
        }
    }

    /**
     * 中序遍历
     */
    public static void inV2(TreeNode root) {
        if (root == null) {
            return;
        }

        inV2(root.left);
        System.out.print(root.val+"  ");
        inV2(root.right);
    }

    /**
     * 随机生成平衡二叉树
     * @param maxSize 最大结点树
     * @param maxValue 结点最大值（不含）
     * @return 树的根结点
     */
    public static TreeNode<Integer> generateBalanceIntValueTree(int maxSize, int maxValue) {
        Random random = new Random();
        int size = random.nextInt(maxSize); // tree 的节点树
        if (size == 0) {
            return null;
        }

        int NodeValue = random.nextInt(maxValue);
        TreeNode<Integer> root = new TreeNode<>(NodeValue);
        size--;

       /* 模拟栈结构 */
        int index = 0;
        TreeNode[] stack = new TreeNode[maxSize];
        stack[index++] = root;
        while (size > -1) {
            TreeNode node = stack[--index];
            node.left = new TreeNode<>(random.nextInt(maxValue));
            stack[index++] = node.left;
            size -- ;

            if (size < 0) {
                break;
            }

            node.right = new TreeNode<>(random.nextInt(maxValue));
            stack[index++] = node.right;
            size -- ;
        }
        return root;
    }

    /**
     * 中序遍历
     */
    private static List<Integer> in(TreeNode<Integer> root) {
        if (root == null) {
            return null;
        }

        List<Integer> list = new LinkedList<>();

        List<Integer> leftList = in(root.left);
        if (leftList!=null && !leftList.isEmpty()) {
            list.addAll(leftList);
        }

        list.add(root.val);

        List<Integer> rightList = in(root.right);
        if (rightList!=null && !rightList.isEmpty()) {
            list.addAll(rightList);
        }

        return list;
    }

    /**
     * 中序升序就是二叉排序树
     */
    private static boolean isBinarySearchTreeV2 (TreeNode<Integer> root) {
        List<Integer> list = in(root);
        if (list==null || list.isEmpty()) return true;

        ArrayList<Integer> arrayList = new ArrayList<>(list);
        int size =  arrayList.size();
        for (int i = 1; i < size; i++) {
            if (arrayList.get(i-1) >= arrayList.get(i) ) {
                return false;
            }
        }

        return true;
    }

    private static boolean isBinarySearchTree (TreeNode<Integer> root) {
        if (root == null) {
            return true;
        }

        if (root.left == null && root.right==null) return true;

        return processBST(root).isBST;
    }

    private static BinarySearchTreeInfo processBST(TreeNode<Integer> root) {
        if (root == null) {
            /*此时是二叉搜索树
            * 但是最大值最小值返回什么都不合适: 0 结点有负值不合适；int的最大和最小，结点中若有不合适
            * 故不创建对象返回*/
            return null;
        }

        if (root.left == null && root.right==null) {
            return new BinarySearchTreeInfo(true, root.val, root.val);
        }

        BinarySearchTreeInfo leftBinarySearchTreeInfo = processBST(root.left);
        BinarySearchTreeInfo rightBinarySearchTreeInfo = processBST(root.right);
        BinarySearchTreeInfo bstInfo = new BinarySearchTreeInfo(false, root.val, root.val);
        /*（左子树是否满足条件）左子树空 直接就满足二叉搜索，不空取属性
        * （右子树是否满足条件）右子树空 直接就满足二叉搜索 不空取属性
        * （当前树是否满足条件）左子树不空比较结点与左子树的最大值，右子树不空比较右子树的最小值*/
        if ((leftBinarySearchTreeInfo==null || (leftBinarySearchTreeInfo.isBST && root.val>leftBinarySearchTreeInfo.maxValue))
        &&  (rightBinarySearchTreeInfo==null || (rightBinarySearchTreeInfo.isBST && root.val<rightBinarySearchTreeInfo.minValue))) {
            bstInfo.setBST(true);
        }

        if (leftBinarySearchTreeInfo!=null) {
            bstInfo.setMaxValue(Math.max(bstInfo.getMaxValue(), leftBinarySearchTreeInfo.maxValue));
            bstInfo.setMinValue(Math.min(bstInfo.getMinValue(), leftBinarySearchTreeInfo.minValue));
        }

        if (rightBinarySearchTreeInfo!=null) {
            bstInfo.setMaxValue(Math.max(bstInfo.getMaxValue(), rightBinarySearchTreeInfo.getMaxValue()));
            bstInfo.setMinValue(Math.min(bstInfo.getMinValue(), rightBinarySearchTreeInfo.getMinValue()));
        }

        return bstInfo;
    }

    private static class BinarySearchTreeInfo{
        private boolean isBST;//是否二插搜索树
        private int minValue;
        private int maxValue;

        public BinarySearchTreeInfo() {
        }

        public BinarySearchTreeInfo(boolean isBST, int minValue, int maxValue) {
            this.isBST = isBST;
            this.minValue = minValue;
            this.maxValue = maxValue;
        }

        public boolean isBST() {
            return isBST;
        }

        public void setBST(boolean BST) {
            isBST = BST;
        }

        public int getMaxValue() {
            return maxValue;
        }

        public void setMaxValue(int maxValue) {
            this.maxValue = maxValue;
        }

        public int getMinValue() {
            return minValue;
        }

        public void setMinValue(int minValue) {
            this.minValue = minValue;
        }
    }

}
